package com.ruoyi.learn.java.algorithm.searching;

/**
 * 二叉搜索树 (Binary Search Tree) 的 Java 实现
 * @param <T> 可比较的泛型类型
 */
public class BinarySearchTree<T extends Comparable<T>> {

    // 树的根节点
    private Node root;

    // 节点内部类
    private class Node {
        T data;
        Node left;
        Node right;

        public Node(T data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

    // ------------------- 构造函数 -------------------
    public BinarySearchTree() {
        this.root = null;
    }

    // ------------------- 基本操作 -------------------

    /**
     * 插入一个元素到 BST
     * @param data 要插入的数据
     */
    public void insert(T data) {
        if (data == null) {
            throw new IllegalArgumentException("Cannot insert null data");
        }
        root = insertRecursive(root, data);
    }

    // 递归插入辅助方法
    private Node insertRecursive(Node node, T data) {
        // 基础情况：如果节点为空，创建一个新节点
        if (node == null) {
            return new Node(data);
        }

        // 递归插入到左子树或右子树
        int compareResult = data.compareTo(node.data);
        if (compareResult < 0) {
            node.left = insertRecursive(node.left, data);
        } else if (compareResult > 0) {
            node.right = insertRecursive(node.right, data);
        }
        // 如果相等，BST 通常不允许重复，因此不插入（也可以选择插入到左或右，这里选择忽略）
        // 可以根据需求修改此行为

        return node;
    }

    /**
     * 查找 BST 中是否存在某个元素
     * @param data 要查找的数据
     * @return 如果找到返回 true，否则返回 false
     */
    public boolean search(T data) {
        if (data == null) {
            return false;
        }
        return searchRecursive(root, data);
    }

    // 递归查找辅助方法
    private boolean searchRecursive(Node node, T data) {
        if (node == null) {
            return false;
        }

        int compareResult = data.compareTo(node.data);
        if (compareResult == 0) {
            return true;
        } else if (compareResult < 0) {
            return searchRecursive(node.left, data);
        } else {
            return searchRecursive(node.right, data);
        }
    }

    /**
     * 删除 BST 中的某个元素
     * @param data 要删除的数据
     */
    public void delete(T data) {
        if (data == null) {
            throw new IllegalArgumentException("Cannot delete null data");
        }
        root = deleteRecursive(root, data);
    }

    // 递归删除辅助方法
    private Node deleteRecursive(Node node, T data) {
        if (node == null) {
            return null; // 数据不存在
        }

        int compareResult = data.compareTo(node.data);
        if (compareResult < 0) {
            node.left = deleteRecursive(node.left, data);
        } else if (compareResult > 0) {
            node.right = deleteRecursive(node.right, data);
        } else {
            // 找到要删除的节点
            // 情况 1: 节点没有子节点或只有一个子节点
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }

            // 情况 2: 节点有两个子节点
            // 找到右子树中的最小值节点（中序后继）
            node.data = findMin(node.right).data;
            // 删除右子树中的最小值节点
            node.right = deleteRecursive(node.right, node.data);
        }
        return node;
    }

    /**
     * 查找 BST 中的最小值
     * @return 最小值，如果树为空则返回 null
     */
    public T findMin() {
        if (root == null) {
            return null;
        }
        return findMin(root).data;
    }

    // 查找以 node 为根的子树中的最小值节点
    private Node findMin(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    /**
     * 查找 BST 中的最大值
     * @return 最大值，如果树为空则返回 null
     */
    public T findMax() {
        if (root == null) {
            return null;
        }
        return findMax(root).data;
    }

    // 查找以 node 为根的子树中的最大值节点
    private Node findMax(Node node) {
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    // ------------------- 遍历操作 -------------------

    /**
     * 中序遍历 (In-order Traversal): 左 -> 根 -> 右
     * 对于 BST，中序遍历会得到一个有序的序列
     */
    public void inOrderTraversal() {
        System.out.print("In-order: ");
        inOrderRecursive(root);
        System.out.println();
    }

    private void inOrderRecursive(Node node) {
        if (node != null) {
            inOrderRecursive(node.left);
            System.out.print(node.data + " ");
            inOrderRecursive(node.right);
        }
    }

    /**
     * 前序遍历 (Pre-order Traversal): 根 -> 左 -> 右
     */
    public void preOrderTraversal() {
        System.out.print("Pre-order: ");
        preOrderRecursive(root);
        System.out.println();
    }

    private void preOrderRecursive(Node node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preOrderRecursive(node.left);
            preOrderRecursive(node.right);
        }
    }

    /**
     * 后序遍历 (Post-order Traversal): 左 -> 右 -> 根
     */
    public void postOrderTraversal() {
        System.out.print("Post-order: ");
        postOrderRecursive(root);
        System.out.println();
    }

    private void postOrderRecursive(Node node) {
        if (node != null) {
            postOrderRecursive(node.left);
            postOrderRecursive(node.right);
            System.out.print(node.data + " ");
        }
    }

    // ------------------- 辅助方法 -------------------

    /**
     * 检查 BST 是否为空
     * @return 如果为空返回 true，否则返回 false
     */
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * 获取树的高度
     * @return 树的高度
     */
    public int height() {
        return heightRecursive(root);
    }

    private int heightRecursive(Node node) {
        if (node == null) {
            return -1; // 空树高度为 -1，或者返回 0，根据定义
        }
        return 1 + Math.max(heightRecursive(node.left), heightRecursive(node.right));
    }

    /**
     * 清空整个 BST
     */
    public void clear() {
        root = null;
    }

    // ------------------- 主函数用于测试 -------------------
    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();

        // 插入元素
        int[] values = {50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45};
        System.out.println("Inserting values: ");
        for (int val : values) {
            System.out.print(val + " ");
            bst.insert(val);
        }
        System.out.println();

        // 遍历
        bst.inOrderTraversal();    // 应该输出有序序列
        bst.preOrderTraversal();
        bst.postOrderTraversal();

        // 查找
        System.out.println("Search 40: " + bst.search(40)); // true
        System.out.println("Search 100: " + bst.search(100)); // false

        // 查找最值
        System.out.println("Min value: " + bst.findMin()); // 10
        System.out.println("Max value: " + bst.findMax()); // 80

        // 删除
        System.out.println("Deleting 20 (leaf node)");
        bst.delete(20);
        bst.inOrderTraversal();

        System.out.println("Deleting 30 (node with two children)");
        bst.delete(30);
        bst.inOrderTraversal();

        System.out.println("Deleting 50 (root)");
        bst.delete(50);
        bst.inOrderTraversal();

        // 高度
        System.out.println("Height of the tree: " + bst.height());
    }
}
